Ngày 30 tháng 3 năm 1970, người đứng đầu Du kích Nhân dân Sarawak tại tỉnh thứ Nhất của Sarawak là Văn Minh Quyền thành lập Đảng Cộng sản Bắc Kalimantan.[1][23] Tuy nhiên, ngày 19 tháng 9 năm 1971 được chọn làm ngày thành lập chính thức của đảng này nhằm trùng với Hội nghị Pontianak được tổ chức vào ngày 17–19 tháng 9 năm 1965. Mặc dù trong Hội nghị tại Pontianak được cho là nền tảng của phong trào cộng sản Sarawak, song không có ai tham dự hội nghị là cộng sản. Thay vào đó, họ gồm các thành viên Liên minh Tự do tả khuynh và "những thành viên O" của Hội Thanh niên Tiên tiến. Mặc dù họ đã thảo luận về việc lập một đảng cộng sản tại Sarawak, song họ trì hoãn thực hiện cho đến năm 1971 do tình hình chính trị căng thẳng tại Indonesia.[23]